package com.lisp.algorithm.sort;

import java.util.Arrays;

import com.lisp.algorithm.util.Assert;

public class Heap {
    
    public static void main(String[] args) {
        int a[] = {10, 8, 8, 7, 20, 3, -1, 0};
        Heap heap = new Heap(a);
        heap.increase(0, 28);
        heap.extractMaximum();
        heap.insert(5);
        for(int i=0; i<a.length; i++) {
            System.out.println(heap.extractMaximum());
        }
    }

    private int data[];
    
    private int heapSize;
    
    public Heap(int a[]) {
        this.data = Arrays.copyOf(a, a.length);
        this.heapSize = a.length;
        buildHeap();
    }
    
    public int extractMaximum() {
        if(heapSize < 1) {
            throw new RuntimeException("heap underflow");
        }
        
        int ret = data[0];
        
        data[0] = data[heapSize-1];
        heapSize = heapSize - 1;
        maxHeapify(0);
        
        return ret;
    }
    
    public void increase(int i, int newVal) {
        Assert.isTrue(i < heapSize);
        Assert.isTrue(newVal > data[i]);
        
        data[i] = newVal;
        
        while(i>0) {
            int parentIndex = (i-1) / 2;
            if(data[parentIndex] < newVal) {                
                swap(i, parentIndex);
                i = parentIndex;
            }
        }
    }
    
    public void insert(int val) {
        heapSize++;
        data[heapSize-1] = val;
        
        int index = heapSize-1; 
        int parentIndex = (index - 1) / 2;
        while(index > 0 && data[parentIndex] < val) {
            swap(index, parentIndex);
            index = (index - 1) / 2;
        }
    }
    
    private void buildHeap() {
        for(int i=(heapSize-1)/2; i>=0; i--) {
            maxHeapify(i);
        }
    }
    
    private void maxHeapify(int i) {
        int largestIndex = i;
        int largestValue = data[i];
        
        int leftIndex = 2*i+1;
        if(leftIndex < heapSize && data[leftIndex] > largestValue) {
            largestIndex = leftIndex;
            largestValue = data[leftIndex];
        }
        
        int rightIndex = 2*i+2;
        if(rightIndex < heapSize && data[rightIndex] > largestValue) {
            largestIndex = rightIndex;
        }
        
        if(largestIndex != i) {
            swap(i, largestIndex);
            maxHeapify(largestIndex);
        }
    }
    
    private void swap(int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}
